// 二叉查找树
#include <stdio.h>
#include <stdlib.h>
#include "../include/bitree.h"

bitree_node_ptr new_bitree_node(int data)
{
    bitree_node_ptr node = (bitree_node_ptr)malloc(sizeof(bitree_node_t));
    if (node == NULL)
    {
        return NULL;
    }
    node->data = data;
    node->parent = NULL;
    node->lchild = node->rchild = NULL;
    return node;
}

bitree_node_t *get_left_max(bitree_node_t *c)
{
    bitree_node_t *t = c->lchild;
    while(t!=NULL)
    {
        if (t->rchild == NULL)
            return t;
        t = t->rchild;
    }
    return t;
}

// 二叉树插入
int bitree_insert(bitree_t *root, int data)
{
    bitree_node_ptr node = new_bitree_node(data);
    if(*root == NULL)
    {
        *root = node;
        return 0;
    }

    bitree_node_ptr tmp = *root;
    while(tmp != NULL)
    {
        if(data < tmp->data)
        {
            if (tmp->lchild == NULL)
            {
                tmp->lchild = node;
                node->parent = tmp;
                break;
            }
            tmp = tmp->lchild;
        } else if (data > tmp->data)
        {
            if (tmp->rchild == NULL)
            {
                tmp->rchild = node;
                node->parent = tmp;
                break;
            }
            tmp = tmp->rchild;
        } else {
            fprintf(stdout, "data %d exist.\n", data);
            break;
        }
    }

    return 0;
}

int bitree_delete(bitree_t *root, int data)
{
    bitree_node_ptr tmp = *root;
    while(tmp != NULL)
    {
        if (data < tmp->data)
            tmp = tmp->lchild;
        else if (data > tmp->data)
            tmp = tmp->rchild;
        else 
            break;
    }
    if (tmp == NULL)
    {
        printf("not found %d\n", data);
        return 1;
    }

    bitree_node_t *lm = get_left_max(tmp);
    if (lm == NULL)
    {
        
    }
    return 0;
}

bitree_node_t* get_min_node(bitree_t root)
{
    while(root != NULL)
    {
        if (root->lchild == NULL)
            return root;
        root = root->lchild;
    }
    return NULL;
}

bitree_node_t* get_max_node(bitree_t root)
{
    while(root != NULL)
    {
        if (root->rchild == NULL) 
            return root;
        root = root->rchild;
    }
    return NULL;
}

// 前序遍历
void bitree_pre_order_print(bitree_t root)
{
    if(root != NULL)
    {
        printf("%d, ", root->data);
        bitree_pre_order_print(root->lchild);
        bitree_pre_order_print(root->rchild);
    }
}

// 中序遍历
void bitree_in_order_print(bitree_t root)
{
    if(root != NULL)
    {
        bitree_in_order_print(root->lchild);
        printf("%d, ", root->data);
        bitree_in_order_print(root->rchild);
    }
}

// 后序遍历
void bitree_post_order_print(bitree_t root)
{
    if(root != NULL)
    {
        bitree_post_order_print(root->lchild);
        bitree_post_order_print(root->rchild);
        printf("%d, ", root->data);
    }
}